package com.lwl.Algorithmic_data_structure.二叉树递归套路;

public class 是否搜索二叉树 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public boolean is_BST(TreeNode root){
        return process(root).isBst;
    }

    private Ret process(TreeNode root) {
        if (root == null){
            return new Ret(true,Long.MIN_VALUE,Long.MAX_VALUE);
        }
        Ret left = process(root.left);
        Ret right = process(root.right);
        if (left.isBst == false || right.isBst == false){
            return new Ret(false,0,0);
        }
        if (left.max >= root.val || right.min <= root.val){
            return new Ret(false,0,0);
        }
        //如果左右子树为空，其返回值 max 为 最小值，min 为 最大值
        //所以这里要去除空姐点的影响
        return new Ret(true, (long)Math.max(right.max,root.val), (long)Math.min(left.min,root.val));
    }
    //这里Ret中的值设置为long是因为leetcode数据样本中有int最大值干扰
    class Ret{
        boolean isBst;
        long max;
        long min;
        public Ret(boolean isBst, long max, long min) {
            this.isBst = isBst;
            this.max = max;
            this.min = min;
        }
    }
}
